import java.util.TreeMap;

/***
 * 字典树
 */
public class Trie {

    private class Node{
        private boolean isWord;
        private TreeMap<Character,Node> next;

        public Node(boolean isWord){
            this.isWord = isWord;
            this.next = new TreeMap<>();
        }
        public Node(){
            this(false);
        }
    }

    private Node root;
    private int size;

    public Trie(){
       this.root = new Node();
       this.size = 0;
    }

    public int getSize(){
        return size;
    }
    public boolean isEmpty(){
        return size == 0;
    }

    /***
     * 向字典树种添加一个单词
     * @param word
     */
    public void add(String word){
        Node cur = root;
        for(int i=0;i<word.length();i++){
            Character c = word.charAt(i);
            if(cur.next.get(c) == null){
                cur.next.put(c,new Node());
            }
            cur = cur.next.get(c);
        }
        //先判断此单词是否已经存在
        if(!cur.isWord){
            cur.isWord = true;
            size++;
        }
    }


    /***
     * 判断是否存在此单词
     * @param word
     * @return
     */
    public boolean contains(String word) {
        Node cur = root;
        for(int i=0;i<word.length();i++){
            char c = word.charAt(i);
            if(cur.next.get(c) == null){
                return false;
            }
            cur = cur.next.get(c);
        }
        //若每个字母都存在,也不能直接返回true,还要判断最后一个节点的isWord属性是否为true
        return cur.isWord;
    }

    private boolean isPrefix(String prefix){
        Node cur = root;
        for(int i=0;i<prefix.length();i++){
            char c = prefix.charAt(i);
            if(cur.next.get(c) == null){
                return false;
            }
            cur = cur.next.get(c);
        }
        return true;
    }
}
